package day03;

// 数组中出现次数超过一半的数字



// 方法一：排序算法：涉及到快排sort，其时间复杂度为O(NlogN)
// 排序算法【中间的就是】

//import java.util.Arrays;
//
//public class Main2 {
//    public int MoreThanHalfNum_Solution(int [] array) {
//        // 判空
//        if(array == null || array.length == 0) {
//            return 0;
//        }
//        // 计算数组长度以及半长
//        int len = array.length;
//        int half = len / 2;
//
//        // 进行升序排列
//        // 涉及到快排sort，其时间复杂度为O(NlogN
//        Arrays.sort(array);
//
//        // 找中间的数字
//        // half直接就是超过一半的数组下标
//        int midNum = array[half];
//
//        // 遍历统计出现次数是否满足题意
//        int count = 0;
//        for (int i = 0; i < len; i++) {
//            if(array[i] == midNum) {
//                count++;
//            }
//        }
//        if(count > half) {
//            return midNum;
//        }
//        return 0;
//    }
//
//}




    // 方法二：相消法：
// 时间复杂度：O(N)
public class Main2 {
    public int MoreThanHalfNum_Solution(int [] array) {
        // 首先判空
        if(array==null || array.length==0) {
            return 0;
        }

        int len = array.length;
        int half = len/2;

        // 进行遍历相消【借助次数】
        int ret = array[0];
        int times = 1;  // 统计次数

        for (int i = 1; i < len; i++) {  // 从1开始：times=1
            // 如果times==0,从新给ret赋值,更新times
            if(times == 0) {
                ret = array[i];
                times++;
            } else if(ret == array[i]) {
                // 相等 times++
                times++;
            } else {
                // 不相等 times--
                times--;
            }
        }

        // 为了以防万一，再次进行统计次数
        times = 0;
        for (int i = 0; i < len; i++) {
            if(ret == array[i]) {
                times++;
            }
        }

        // 返回
        return (times>half)? ret:0;
    }
}

